package com.lry.basic.algorithm.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/7/10
 */
//二叉搜索树 不允许重复数据
public class BiSearchTree {
    Node root;

    boolean insert(Node node){
        if(node==null)return false;
        if(root==null){
            root = node;
            return true;
        }
        Node temp = root;
        Node cur = null;//node应该在cur节点左边或者右边插入
        while(temp!=null){
            cur = temp;
            if(temp.data>node.data){//往左边插入
                temp = temp.left;
            }else if(temp.data<node.data){//往右边插入
                temp = temp.right;
            }else{//相等插入不了
                return false;
            }
        }
        if(cur==null)return false;
        if(node.data>cur.data){
            cur.right = node;
        }else{
            cur.left = node;
        }
        return true;
    }
    public int high(Node node){
        if(node==null)return 0;
        return Math.max(high(node.left),high(node.right))+1;
    }
    public void inOrder(Node root){
        if(root!=null){
            inOrder(root.left);
            System.out.print(root.data+" ");
            inOrder(root.right);
        }
    }

    public int min(Node root){
        if(root==null)return 0;
        Node temp = root;
        Node cur = null;
        while(temp!=null){
            cur=temp;
            temp = temp.left;
        }
        return cur.data;
    }
    public int max(Node root){
        if(root==null)return 0;
        Node temp = root;
        Node cur = null;
        while(temp!=null){
            cur=temp;
            temp = temp.right;
        }
        return cur.data;
    }
    public boolean find(int find){
        Node temp = root;
        while(temp!=null){
            if(temp.data>find){//往左边走
                temp = temp.left;
            }else if(temp.data<find){//往右边走
                temp=temp.right;
            }else{
                return true;
            }
        }
        return false;
    }
    public Node findNode(int find){
        Node temp = root;
        Node cur = null;
        while(temp!=null){
            cur = temp;
            if(temp.data>find){//往左边走
                temp = temp.left;
            }else if(temp.data<find){//往右边走
                temp=temp.right;
            }else{
                return cur;
            }
        }
        return cur;
    }
    public Node parent(int par){
        Node temp = root;
        Node cur = null;
        while(temp!=null){
            if(temp.data>par){//往左边走
                cur = temp;
                temp = temp.left;
            }else if(temp.data<par){//往右边走
                cur = temp;
                temp=temp.right;
            }else{
                return cur;
            }
        }
        return cur;
    }
    //叶节点直接删除
    //只有左孩子或者只有右孩子，用左孩子或者右孩子顶替他
    //x既有左孩子又有右孩子，使用右孩子顶替x，并把x的左子树挂在x右孩子一直往左走走到null的那个节点上
    public boolean delete(int del){
        Node find = findNode(del);
        if(find==null)return false;

        //删除的节点为叶节点
        if(find.left==null&&find.right==null){
            Node parent = parent(del);//找到父亲
            if(parent==null){//删除的节点是根节点
                root = null;
                return true;
            }
            //确定是左节点还是右节点
            if(parent.left!=null){
                if(parent.left.data==del){
                    parent.left=null;
                    return true;
                }
            }
            if(parent.right!=null){
                if(parent.right.data==del){
                    parent.right=null;
                    return true;
                }
            }
        }
        //该节点只有左孩子，用左孩子顶替他
        if(find.left!=null&&find.right==null){
            Node left = find.left;//左孩子
            Node parent = parent(del);//父亲
            if(parent==null){//删除的节点是根节点
                root = root.left;
                return true;
            }
            if(parent.right!=null){
                if(parent.right.data==del){
                    parent.right = left;
                    return true;
                }
            }
            if(parent.left!=null){
                if(parent.left.data==del){
                    parent.left = left;
                    return true;
                }
            }
        }

        //该节点只有右孩子，用右孩子顶替他
        if(find.left==null&&find.right!=null){
            Node right = find.right;//右孩子
            Node parent = parent(del);//父亲
            if(parent==null){//删除的节点是根节点
                root = root.right;
                return true;
            }
            if(parent.right!=null){
                if(parent.right.data==del){
                    parent.right = right;
                    return true;
                }
            }
            if(parent.left!=null){
                if(parent.left.data==del){
                    parent.left = right;
                    return true;
                }
            }
        }

        //该节点既有左孩子又有右孩子
        if(find.left!=null&&find.right!=null){
            Node right = find.right;//用右孩子顶替他
            Node left = find.left;
            Node parent = parent(del);//父亲
            if(parent==null){//删除的节点是根节点
                root = right;
                while(right.left!=null){
                    right = right.left;
                }
                right.left = left;
                return true;
            }
            if(parent.left!=null){
                if(parent.left.data==del){
                    parent.left = right;
                    while(right.left!=null){
                        right = right.left;
                    }
                    right.left = left;
                    return true;
                }
            }

            if(parent.right!=null){
                if(parent.right.data==del){
                    parent.right = right;
                    while(right.left!=null){
                        right = right.left;
                    }
                    right.left = left;
                    return true;
                }
            }
        }
        return false;
    }
    public boolean isValidBST(Node root) {
        if(root!=null){
            if(root.left!=null&&max(root.left)>=root.data)return false;
            if(root.right!=null&&min(root.right)<=root.data)return false;
            return isValidBST(root.left)&&isValidBST(root.right);
        }
        return true;
    }


    public boolean isSame(Node root1,Node root2){
        if(root1!=null&&root2==null)return false;
        if(root1==null&&root2!=null)return false;
        if(root1==null&&root2==null)return true;

        if(root1.data!=root2.data)
            return false;
        else {
            //&&是关键
            return  isSame(root1.left,root2.left)&&isSame(root1.right,root2.right);
        }
    }
    //有没有一条路径的和等于sum
    //dfs
    public boolean hasPathSum(Node root, int sum) {
        if(root==null)return false;
        sum-=root.data;
        if(root.left==null&&root.right==null)
            return sum==0;
        return hasPathSum(root.left,sum)||hasPathSum(root.right,sum);
    }


    List<String> res = new ArrayList<>();
    public List<String> binaryTreePaths(Node root) {
        if(root==null) return res;
        dfs(root,"");
        return res;
    }
    public  void dfs(Node root,String str){
        if(root.left==null&&root.right==null){
            res.add(str+root.data);
        }
        if(root.left!=null){
            dfs(root.left,str+root.data+"->");
        }
        if(root.right!=null){
            dfs(root.right,str+root.data+"->");
        }
    }



    //找到pq最近公共祖先
    public Node lowestCommonAncestor(Node root,int p,int q){
        //pq全在右子树
        //pq全在左子树
        //else 找到了
        if(p>root.data&&q>root.data){
            return lowestCommonAncestor(root.right,p,q);
        }else if(p<root.data&&q<root.data){
            return lowestCommonAncestor(root.left,p,q);
        }else{
            return root;
        }
    }
    static class Node{
        int data;
        Node left;
        Node right;
        Node(int data){this.data=data;}

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    public static void main(String[] args) {
        BiSearchTree tree = new BiSearchTree();
        tree.insert(new Node(4));
        tree.insert(new Node(2));
        tree.insert(new Node(1));
        tree.insert(new Node(3));
        tree.insert(new Node(6));
        tree.insert(new Node(5));
        tree.insert(new Node(7));
        System.out.println(tree.high(tree.root));
//        tree.delete(2);
        tree.inOrder(tree.root);
        System.out.println(tree.isValidBST(tree.root));
        System.out.println(tree.hasPathSum(tree.root, 7));
//        List<String>list = tree.binaryTreePaths(tree.root);
//        for (String str:list) {
//            System.out.println(str);
//        }
        System.out.println(tree.lowestCommonAncestor(tree.root, 5, 7).data);
    }
}
